#ifndef lfqueue_h__
#define lfqueue_h__
#include "atomic.h"

namespace gecko
{

// a lock-free queue.
// fast, non-blocking queue for thread safe queue operations.
template<typename T>
class LFQueue
{
public:
	// queue node.
	class Node
    {
	public:
		// pointer to the next node in the queue.
        Node* Next;

		// the data contained in the node.
        T Data;
    };

    // construct an empty queue.
    LFQueue();

    // destructor.
    virtual ~LFQueue();

    // enqueue operation.
    void Enqueue(const T& item);

    // dequeue operation.
	// returns pointer to node removed front the front. NULL if queue is empty.
    Node* Dequeue();

    // Clear the queue.
    void Clear();

private:
    Node* m_Head;
	Node* m_Tail;

#if defined(ENABLE_CRITICAL_SECTION)
	CriticalSection m_critSection;
#endif
};

template<typename T>
LFQueue<T>::LFQueue()
{
    m_Head = new Node;	// dummy head node
	m_Head->Next = 0;
	m_Tail = m_Head;
}

template<typename T>
LFQueue<T>::~LFQueue()
{
	delete m_Head;
}

template<typename T>
void LFQueue<T>::Enqueue(const T& item)
{
#if defined(ENABLE_CRITICAL_SECTION)
	m_critSection.Begin();
#endif

	Node* node = new Node;
    node->Data = item;
	node->Next = 0;

    volatile Node** vtail =  0;
	volatile Node** vtailNext =  0;
    volatile Node* vnode = (volatile Node*)node;
	volatile Node* oldTail = 0;
	bool updatedLinks = false;
    while ( !updatedLinks )
    {
		vtail = (volatile Node**)&m_Tail;
		vtailNext = (volatile Node**)&m_Tail->Next;
		oldTail = *vtail;

		// try and set tail->next to point to new node
		updatedLinks = Atomic::CompareSwapPtr((volatile void**)vtailNext, (void*)0, (void*)vnode);
    };

	// update tail pointer to point to new node
	Atomic::CompareSwapPtr((volatile void**)vtail, (void*)oldTail, (void*)vnode);

#if defined(ENABLE_CRITICAL_SECTION)
	m_critSection.End();
#endif
}

template<typename T>
typename LFQueue<T>::Node* LFQueue<T>::Dequeue()
{
#if defined(ENABLE_CRITICAL_SECTION)
	m_critSection.Begin();
#endif

	volatile Node** vheadNext = (volatile Node**)&m_Head->Next;
	volatile Node* vhead = 0;
	volatile Node* vnode = 0;
	volatile Node** vtail =  0;
	bool updatedLinks = false;
    while ( !updatedLinks )
	{
		vnode = *vheadNext;
		if ( !vnode )
		{
#if defined(ENABLE_CRITICAL_SECTION)
			m_critSection.End();
#endif
			return 0;
		}

		vtail = (volatile Node**)&m_Tail;
		vhead = (volatile Node*)m_Head;
		volatile Node* next = vnode->Next;

		// try and set head to point to deleted node's next pointer
		updatedLinks = Atomic::CompareSwapPtr((volatile void**)vheadNext, (void*)vnode, (void*)next);
	}

	// if tail is vnode: tail is Head
	Atomic::CompareSwapPtr((volatile void**)vtail, (void*)vnode, (void*)vhead);

#if defined(ENABLE_CRITICAL_SECTION)
	m_critSection.End();
#endif

	return (Node*)vnode;
}

template<typename T>
void LFQueue<T>::Clear()
{
	Node* node = Dequeue();
	while ( node )
	{
		delete node;
		node = Dequeue();
	}

	m_Head->Next = 0;
	m_Tail = m_Head;
}

}

#endif